import java.util.Arrays;
import java.util.Random;

/**
 * @program: data_structures_algorithms
 * @description: 快速排序-随机基准值
 * @author: lld
 * @create: 2021-4-10 20:07
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {7, 1, -1, 10, 2, 32, -21, 6};
        quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
//        int[] bigArray1 = new int[10000000];
//        for (int i = 0; i < bigArray1.length; i++) {
//            bigArray1[i] = (int) (Math.random() * 1000000000);
//        }
//        long start = System.currentTimeMillis();
//        quickSort(bigArray1, 0, bigArray1.length - 1);
//        long end = System.currentTimeMillis();
//        System.out.println("10000000个数据排序时间(毫秒):" + (end - start));//双1500，单1400
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }
        int pivot = randomizedPartition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    /**
     * @Description: 随机选一个作为基准值
     **/
    public static int randomizedPartition(int[] arr, int left, int right) {
        // 随机选一个作为基准值
        //介于0（含）和指定值（不包括）,生成访问为：[left,right]
        int i = new Random().nextInt(right - left + 1) + left;
//        与数组第一个元素交换，便于遍历数组交换
        swap(arr, left, i);
        return partition(arr, left, right);
    }

    /**
     * @Description: 根据基准值划分
     **/
    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int mark = left;
        for (int i = left + 1; i <= right; i++) {
            if (arr[i] < pivot) {
                mark++;
                swap(arr, i, mark);
            }
        }
//        基准位置和与leftright重合位置交换
        swap(arr, left, mark);
        return mark;
    }
    /**
     * @Description: 交换
     **/
    public static void swap(int[] arr, int i, int j) {
        if(arr[i] ==arr[j]) return;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
